package q42_trap;

import java.util.Deque;
import java.util.LinkedList;

public class Solution_1 {
    public static void main(String[] args) {
        int[] arr = {2,0,1,2};
        System.out.println(trap(arr));
    }

    public static int trap(int[] height) {
        int res = 0;// 存水总量
        Deque<Integer> stack = new LinkedList<Integer>();

        int n = height.length;
        for (int i = 0; i < n; ++i) {
            // 当栈不为空，并且数值开始递增时，开始计算数值
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                // 先弹出了栈最上面的值
                int top = stack.pop();
                // 如果栈空了，就直接break，可以绘图研究
                if (stack.isEmpty()) {
                    break;
                }
                // 左侧的下标是栈的顶层数值
                int left = stack.peek();
                // 当前位置离左侧长度的计算方法
                int currWidth = i - left - 1;
                // 当前的高度，应该是左右两侧柱子中取一个低的高度，同时要减去top，也就是弹出的最上面的值，这里可以理解为当前柱子的前一个
                int currHeight = Math.min(height[left], height[i]) - height[top];
                // 计算水柱
                res += currWidth * currHeight;
            }

            // 空栈 或者 数值在 *递减* 的时候 ，将元素押入栈（数值为0也算，也需要压入栈）
            stack.push(i);
        }



        return res;
    }
}
